#include<stdio.h>

int ChooseMid(int* a, int left, int right)
{
	int mid = (left + right) / 2;
	if (a[left] < a[mid])
	{
		if (a[mid] < a[right])
			return mid;
		else
		{
			return right;
		}
	}
	else
	{
		if (a[left] < a[right])
			return left;
		else
		{
			return right;
		}
	}
}

void Swap(int* pa, int* pb)
{
	int tmp = *pa;
	*pa = *pb;
	*pb = tmp;
}

void QuickSort3(int* a, int left, int right)
{
	if (left >= right)
		return;
	int begin = left;
	int end = right;
	int keyi = ChooseMid(a, left, right);
	Swap(&a[keyi], &a[left]);
	int first = left;
	int second = left + 1;
	while (second <= right)
	{
		if (a[second] < a[keyi])
		{
			++first;
			Swap(&a[first], &a[second]);
		}
		++second;
	}
	Swap(&a[keyi], &a[first]);
	keyi = first;
	QuickSort3(a, begin, keyi - 1);
	QuickSort3(a, keyi + 1, end);
}

void PrintArray(int* a, int n)
{
	for (int i = 0; i < n; ++i)
	{
		printf("%d ", a[i]);
	}
	printf("\n");
}

int main()
{
	int a[] = { 6,1,2,6,9,3,4,6,10,8 };
	PrintArray(a, sizeof(a) / sizeof(int));

	QuickSort3(a,0,sizeof(a) / sizeof(int)-1);

	PrintArray(a, sizeof(a) / sizeof(int));

}
